
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-02
 * Time: 15:08
 */

class TreeNode {
     int val;
     TreeNode2 left;
     TreeNode2 right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode2 left, TreeNode2 right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

/**
 * 前序非递归
 */
public class Main {
    public List<Integer> preorderTraversal(TreeNode2 root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode2> stack=new Stack<>();
        if(root==null){
            return list;
        }
        TreeNode2 treeNode=root;
        //两个条件:节点不为空或栈不为空都得继续
        while(treeNode!=null||!stack.isEmpty()){
            while(treeNode!=null){
                //节点不为空就先push入栈再打印
                stack.add(treeNode);
                list.add(treeNode.val);
                treeNode=treeNode.left;
            }
            //节点为空就继续遍历节点右子树
            treeNode=stack.pop().right;
        }
        return list;
    }
}

